/*
Date:20210609 16:16PM
ley:就是mink问题，快排解决
*/
class Solution {
public:

    void ksort(vector<int>& arr, int l, int r ,const int k,vector<int>&v)
    {
        
        if(l>r){return;}
        int p=arr[l];
        int i=l;
        int j=r;
        while(i<j)
        {
            while(i<j&&p<=arr[j])
            {
                j--;
            }
            while(i<j&&p>=arr[i])
            {
                i++;
            }
            if(i<j)
            {
                swap(arr[i],arr[j]);
            }
            
        }
        swap(arr[i],arr[l]);

        if(i==k-1)
        {
            for(int j=0;j<=i;j++)
            {
                v.push_back(arr[j]);
            }
        }
        else
        {
            ksort(arr, l, i-1 , k,v);
            ksort(arr, i+1, r , k,v);
        }
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) 
    {
        if(k==arr.size()){return arr;}
        vector<int>v;
        ksort(arr,0,arr.size()-1,k,v);
        return v;

    }
};